/**
 * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 *
 * 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
 *
 *
 *
 * 链接：https://leetcode.cn/problems/longest-increasing-subsequence
 */
//题解：https://labuladong.gitee.io/algo/3/25/70/
class LengthOfLIS {
    /**
     * 法一：动态规划
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        int len=nums.length;
        int[] dp=new int[len];
        Arrays.fill(dp,1);
        for(int i=0;i<len;i++) {
            for(int j=0;j<i;j++) {
                if(nums[j]<nums[i]) {
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
        }
       int res=dp[0];
       for(int i=1;i<len;i++) {
           res=Math.max(dp[i],res);
       }
       return res;
    }

    /**
     * 法二：贪心加二分
     *
     * @param nums
     * @return
     */
    public int lengthOfLISBinary(int[] nums) {
        int len=nums.length;
        int[] top=new int[len];
        // 牌堆数初始化为 0
        int piles=0;
        for(int i=0;i<len;i++) {
            // 要处理的扑克牌
            int poker=nums[i];
            /***** 搜索左侧边界的二分查找 *****/
            int left=0;
            int right=piles;
            while(left<right) {
                int mid=left+((right-left)>>>1);
                if(top[mid]>poker) {
                    right=mid;
                } else if(top[mid]<poker) {
                    left=mid+1;
                } else {
                    right=mid;
                }
            }
            /*********************************/

            // 没找到合适的牌堆，新建一堆
            if(left==piles)
                piles++;
            top[left]=poker;
        }
        // 牌堆数就是 LIS 长度
        return piles;
    }
}